//
//  IsInterleave.swift
//  LeetCodeSummary
//
//  Created by 彭西西 on 2020/7/19.
//  Copyright © 2020 WangYonghe. All rights reserved.
//  97. 交错字符串

import UIKit

/*
 97. 交错字符串
 
 给定三个字符串 s1, s2, s3, 验证 s3 是否是由 s1 和 s2 交错组成的。

 示例 1:

 输入: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
 输出: true
 示例 2:

 输入: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
 输出: false
 */

/*
 这道提的正确解法是动态规划
 我们设: f(i,j)表示s1的前i个字符串和s2的前j个字符串是否能组成s3的前i+j个字符串
 
 如果 s1的第i和元素和s3的第i+j和元素相等，那么f(i,j)是否等于true 就取决于s1的前i-1个元素是否能和s1的前j个元素组合成s3的前i+j-1个元素，
 即 f(i,j)取决于f(i-1,j)。如果前者等于true，那么后者也等于true。 s2也是同样的。
 
 所以我们可以推到出动态转移公式：   p = i+j-1
 f(i,j) = f(i-1,j) && s1(i-1)==s3(p)    ||    f(i,j-1) && s2(j-1)==s3(p)
 */


class IsInterleave: NSObject {
    
    /*
     时间复杂度：O(nm)，两重循环的时间代价为 O(nm)。
     空间复杂度：O(nm)，即s1,s2的长度
     */
    func isInterleave(_ s1: String, _ s2: String, _ s3: String) -> Bool {
        let n = s1.count
        let m = s2.count
        let s = s3.count
        if n + m != s {
            return false
        }
        
        var dp = [[Bool]](repeating: [Bool](repeating: false, count: m+1), count: n+1)
        dp[0][0] = true
        
        for i in 0 ... n{
            for j in 0 ... m{
                let p = i + j - 1
                if i > 0 {
                    // dp[i][j] ||  这个条件很重要 当i>0 && j>0 时，后面一个条件直接返回  即 f(i,j)取决于f(i-1,j)。如果前者等于true，那么后者也等于true。 s2也是同样的。
                    dp[i][j] =              dp[i-1][j] && s1[s1.index(s1.startIndex, offsetBy: i-1)] == s3[s3.index(s3.startIndex, offsetBy: p)]
                }
                if j > 0 {
                    dp[i][j] = dp[i][j] || (dp[i][j-1] && s2[s2.index(s2.startIndex, offsetBy: j-1)] == s3[s3.index(s3.startIndex, offsetBy: p)])
                }
                /*这里我们发现dp数组的第i行仅和第i-1行相关，我们可以用滚动数组来动态优化*/
                
            }
        }
        
        return dp[n][m]
    }
    
    //使用滚动数组来进行优化
    /*
    时间复杂度：O(nm)，两重循环的时间代价为 O(nm)。
    空间复杂度：O(m)，即s2的长度
    */
    func isInterleave2(_ s1: String, _ s2: String, _ s3: String) -> Bool {
        let n = s1.count
        let m = s2.count
        let s = s3.count
        if n + m != s {
            return false
        }
        
        var dp = [Bool](repeating: false, count: m+1)
        dp[0] = true
        
        for i in 0 ... n{
            for j in 0 ... m{
                let p = i + j - 1
                if i > 0 {
                    dp[j] = dp[j] && s1[s1.index(s1.startIndex, offsetBy: i-1)] == s3[s3.index(s3.startIndex, offsetBy: p)]
                }
                if j > 0 {
                    dp[j] = dp[j] || dp[j-1] && s2[s2.index(s2.startIndex, offsetBy: j-1)] == s3[s3.index(s3.startIndex, offsetBy: p)]
                }
            }
        }
        
        return dp[m]
    }
}

//有了以下扩展 s1[s1.index(s1.startIndex, offsetBy: i-1)]  ==>>   s1[i-1]
extension String {

    var length: Int {
        return count
    }

    subscript (i: Int) -> String {
        return self[i ..< i + 1]
    }

    func substring(fromIndex: Int) -> String {
        return self[min(fromIndex, length) ..< length]
    }

    func substring(toIndex: Int) -> String {
        return self[0 ..< max(0, toIndex)]
    }

    subscript (r: Range<Int>) -> String {
        let range = Range(uncheckedBounds: (lower: max(0, min(length, r.lowerBound)),
                                            upper: min(length, max(0, r.upperBound))))
        let start = index(startIndex, offsetBy: range.lowerBound)
        let end = index(start, offsetBy: range.upperBound - range.lowerBound)
        return String(self[start ..< end])
    }
}
